// 完全二叉树的节点个数

package Leetcode;

import java.util.Deque;
import java.util.LinkedList;

class Solution_222_1 {
    public int countNodes(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        int count = 0;
        if (root == null)
            return count;
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                TreeNode node = queue.poll();
                count++;
                if (node.left != null)
                    queue.addLast(node.left);
                if (node.right != null)
                    queue.addLast(node.right);
            }
        }
        return count;
    }
}

class Solution_222_2 {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        // 得到二叉树的层数
        int level = 0;
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left;
        }
        // 计算最小节点个数和最大节点个数
        int low = 1 << level;
        int high = (1 << (level + 1)) - 1;

        // while (low < high) {
        //     int mid = (high + low + 1) / 2; // 这里必须+1，否则如果为6和7且6存在则会进行循环
        //     if (find(root, level, mid))
        //         low = mid;
        //     else
        //         high = mid - 1;
        // }
        while (low <= high) {
            int mid = low + (high - low) >> 1; // 这里必须+1，否则如果为6和7且6存在则会进行循环
            if (find(root, level, mid))
                low = mid + 1;
            else
                high = mid - 1;
        }

        return low;
    }

    public boolean find(TreeNode root, int level, int mid) {
        // 判断第level-1位是否为1
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (bits != 0) { // 0表示左子树，1表示右子树
            if ((mid & bits) == 0)
                node = node.left;
            else
                node = node.right;
            bits >>= 1;
        }
        return node != null;
    }
}